package com.cskaoyan.day02.doubled;

import com.cskaoyan.day02.single.MyLinkedList;

/**
 * @author stone
 * @date 2022/01/28 15:10
 */
public class LinkedList {

    private int size;
    private Node head;
    private Node rear;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void show() {
        if (isEmpty()) {
            System.out.println("链表为空");//抛出异常也行
            return;
        }
        //需要一个额外的标记 → 标记当前结点
        Node current = head;

        while (current != null) {
            System.out.print(current.value + "-->");
            current = current.next;
        }
        System.out.println();
    }

    public boolean add(String value) {
        //value是否等于null  👉 后面就不允许它添加null值
        if (value == null) {
            return false;
        }
        //链表为空
        if (isEmpty()) {
            head = new Node(value);
            rear = head;
        }else {
            //添加结点 👉 添加到rear之后
            rear.next = new Node(value, rear, null);
            rear = rear.next;
        }
        size++;
        return true;
    }

    public boolean remove(String value) {
        if (value == null) {
            return false;
        }
        if (isEmpty()) {
            throw new RuntimeException("链表为空");
        }
        //头结点
        if (value.equals(head.value)) {
            head = head.next;
            head.pre = null;
            size--;
            return true;
        }
        //遍历 👉 头结点已经处理过了，从第二个结点开始继续
        Node current = head.next;
        while (current != null && !value.equals(current.value)) {
            //遍历中止条件 value.equals(current.value)
            //遍历中止条件 current == null
            current = current.next;
        }
        //遍历是为了找目标结点
        //如果链表中不存在这个值的结点
        if (current == null) {
            return false;
        }
        //尾结点
        if (current == rear) {
            rear = rear.pre;
            rear.next = null;
            /*size--;
            return true;*/
        }else {
            //中间结点
            current.pre.next = current.next;
            current.next.pre = current.pre;
            /*size--;
            return true;*/
        }
        size--;
        return true;
    }

    public boolean add(int index, String value) {
        if (index < 0 || index > size) {
            throw new RuntimeException("参数不合法");
        }
        //尾结点位置
        if (index == size) {
            //index==0&& isEmpty也会进入到这里
            return add(value);//add(value)就是在size位置增加新结点
        }
        //头结点位置
        if (index == 0) {
            /*if (isEmpty()) {
                head = new Node(value);
                rear = head;

            }else {
                //新增结点，新结点next指向之前的head、head的pre指向新结点
                head.pre = new Node(value, null, head);
                head = head.pre;
            }*/
            //新增结点，新结点next指向之前的head、head的pre指向新结点
            head.pre = new Node(value, null, head);
            head = head.pre;
            size++;
            return true;

        }

        //中间结点位置
        //index=1~size-1
        //current
        Node current;
        int tag;
        //int tag = 1;
        if (index < size / 2) {//index < size>>1  数字向右移位就是除以2
            //当前结点在前半部分
            current = head.next;
            tag = 1;
            while (tag++ != index) {
                current = current.next;
            }
        }else {
            //当前结点在后半部分
            current = rear;
            tag = size - 1;
            while (tag-- != index) {
                current = current.pre;
            }
        }
        //找到目标结点，将新结点新增在current.pre和current之间
        Node newNode = new Node(value, current.pre, current);
        current.pre.next = newNode;
        current.pre = newNode;
        size++;
        return true;
    }

    public String remove(int index) {
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("参数不合法");
        }
        //头结点
        if (index == 0) {
            //值的获得要在head修改之前
            String value = head.value;
            //如果链表中只有一条记录呢
            if (size == 1) {
                head = null;
                rear = null;
            }else {
                head = head.next;
                head.pre = null;
            }
            size--;
            return value;
        }
        //尾结点
        if (index == size - 1) {
            String value = rear.value;
            //这里不需要考虑size == 1的情况 → 165行到168行已经考虑过了
            rear = rear.pre;
            rear.next = null;
            size--;
            return value;
        }
        Node current = null;
        int tag;
        //中间结点
        if (index < size >> 1) {
            //前半部分 从1开始
            tag = 1;
            current = head.next;
            while (tag++ != index) {
                current = current.next;
            }
        }else {
            //后半部分 size-2
            tag = size - 2;
            current = rear.pre;
            while (tag-- != index) {
                current = current.pre;
            }
        }
        current.pre.next = current.next;
        current.next.pre = current.pre;
        size--;
        return current.value; //current.value是没有问题
    }

    //todo: 当前结点
    public String get(int index) {
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("参数不合法");
        }
        Node current;
        int tag;
        if (index < size >> 1) {
            current = head;
            tag = 0;
            while (tag++ != index) {
                current = current.next;
            }
        }else {
            current = rear;
            tag = size - 1;
            while (tag-- != index) {
                current = current.pre;
            }
        }
        return current.value;
    }

    //todo: 当前结点
    public boolean set(int index, String value) {
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("参数不合法");
        }
        Node current;
        int tag;
        if (index < size >> 1) {
            current = head;
            tag = 0;
            while (tag++ != index) {
                current = current.next;
            }
        }else {
            current = rear;
            tag = size - 1;
            while (tag-- != index) {
                current = current.pre;
            }
        }
        current.value = value;
        return true;
    }

    //todo:
    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        if (isEmpty()) {
            throw new RuntimeException("链表为空");
        }
        Node current = head;
        while (current != null && !value.equals(current.value)) {
            //遍历中止条件 value.equals(current.value)
            //遍历中止条件 current == null
            current = current.next;
        }
        //遍历是为了找目标结点
        //如果链表中不存在这个值的结点
        if (current == null) {
            return false;
        }
        return true;
    }

    public boolean set(String origin, String value) {
        if (origin == null) {
            return false;
        }
        if (isEmpty()) {
            throw new RuntimeException("链表为空");
        }
        Node current = head;
        while (current != null && !origin.equals(current.value)) {
            //遍历中止条件 value.equals(current.value)
            //遍历中止条件 current == null
            current = current.next;
        }
        //遍历是为了找目标结点
        //如果链表中不存在这个值的结点
        if (current == null) {
            return false;
        }
        current.value = value;
        return true;
    }

    //新增了Node → 双向链表的node
    class Node{
        String value;
        Node pre;
        Node next;

        public Node(String value) {
            this.value = value;
        }

        public Node(String value, Node pre, Node next) {
            this.value = value;
            this.pre = pre;
            this.next = next;
        }
    }
}
